package leetcode_1101_1200;

import javax.swing.plaf.PanelUI;
import java.util.Arrays;
import java.util.TreeMap;

public class LeeCode_1170 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(numSmallerByFrequency(new String[]{"cbd"}, new String[]{"zaaaz"})));
    }
    private static int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] ans = new int[queries.length];
        int[] tab = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            tab[i] = f(words[i]);
        }
        Arrays.sort(tab);
        for (int i = 0; i < queries.length; i++) {
            int count = f(queries[i]);
            int index = bigger(tab, count);
            ans[i] = index == -1 ? 0 : words.length - index;
        }
        return ans;
    }
    private static int bigger(int[] tab, int goal){
        int l = 0, r = tab.length - 1;
        while (l < r){
            int m = (l + r) >> 1;
            if (tab[m] <= goal){
                l = m + 1;
            }else {
                r = m;
            }
        }
        if (tab[l] <= goal)
            return -1;
        return l;
    }
    private static int f(String s){
        TreeMap<Character, Integer> map = new TreeMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        return map.firstEntry().getValue();
    }
}